题解 P2921 【[USACO08DEC]在农场万圣节Trick or Treat on the Farm】

发表于 | 更新于

题意:从图中第$i$号节点开始遍历,每个节点存有下一步要去的节点,当遍历的路径出现环时结束遍历并输出路径长度(边权默认为$1$)

这道题很像P2661，那道题用带权并查集求有向图中的最小环，这道题要求的是每个点在有向图中的环的长度或进入环之前经过的点数与环的长度的和。由于并查集经过路径压缩后只能存储它祖先的信息，所以我们开一个$fa$数组记录它的父亲。判断环我们只需判断读入的$a_{i}$与$i$是否祖先节点相同，那么就可以判断是否能构成一个环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}//快读
int ans[300000],f[300000],fa[3000000];
int find(int k){
    if (f[k]==k)return k;
    else return f[k]=find(f[k]);
}//并查集
int main(){
    int n=read();
    for (int i=1;i<=200000;i++)f[i]=i,fa[i]=1;//初始化
    for (int i=1;i<=n;i++){
        int x=read();
        if (find(x)==find(i)){//如果构成环
            int res=1;
            for (int j=x;j!=i;j=fa[j]) res++;//从x->x的父亲-->……直到回到i，其中i~x这条边没算，所以res初值赋为1
            for (int j=x;j!=i;j=fa[j]) ans[j]=res;//给环中的每个节点的答案赋值
            ans[i]=res;//i这个点刚刚没赋值
        }else{
            f[find(i)]=find(x);
            fa[i]=x;
        }
    }//由于i一定是第一次赋值，所以find(i)一定等于i，所以这个循环中的find(i)都可以写成i
    for (int i=1;i<=n;i++) 
        if (ans[i]==0){
            int res=1,j;
            for (j=fa[i];ans[j]==0;j=fa[j])
                res++;
            ans[i]=res+ans[j];
        }//特别处理自身不在环中的点，计算进入环之前经过的点数与环的长度的和
    for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
}